polyformfandomcom-20200213-history
Convex Block
A''' convex block''' is a finite shape taken from base grid with no holes, and no dents. A quasi-convex block may have slight points extending from the surface due to the shape of the base form, but can use a less restrictive definition, such as the centers of the shapes forming a convex shape. Format Notation This section tries to find a simple, concise way to uniquely refer to all blocks for a basic grid. It should minimize the need for wordy descriptions. This makes it easier to talk about them in articles. Size So given a notation, the question is, how many of the base forms are contained in it. This is usually a simple formula from the notation. This section shows the formula. Enumeration Going the other way, trying to find all blocks that have an area N, is a lot trickier. This section gives an algorithm for finding all such blocks. Parity Some grids can be coloured in an alternating black and white "checkerboard" pattern. The difference between the number of each can sometimes be useful for solving puzzles. This section describes if and how the parity of a block can be found from the notation. Polyominoes Polyominoes are based on a square grid, so any convex shape will have corners that are right angles. So a convex block will simply be a rectangle. Notation Describing a rectangle is extreamly basic n \times m, 0 which is a rectangle with sides n and m. Size The size of a rectangle is also basic mathematics \text{area} = nm\, Enumeration For a given size N, it is relatively easy to find all rectangles the have an area of N. #Find all positive divisors of N #Each pair of divisors that multiply to give N is an n,m that forms a rectangle of size N. #If there is an odd number of divisors, N is square, so the remaining divisor makes an n x n square. The total number of blocks of size N is given by the sequence Parity The square grid can be coloured like a checkerboard, alternating black and white squares. The difference between the number of each can sometimes be useful when solving puzzles. For a rectangle n x m \text{Parity}= \begin{cases} 0, & \text{if }n\text{ or }m\text{ is even} \\ 1, & \text{if }n\text{ and }m\text{ are odd} \end{cases} Polyiamonds Polyiamonds are based on the triangular grid, which means the corners of a convex shape can be 60 or 120 degrees. This makes it slightly more complicated to categorize. The key is to notice, in the figure at right, that around a convex block, in black, there are two minimum large triangles that can be formed around it. One pointed up, blue, and one down, red. The additions to the block to form each large triangle are also triangles. Only the smaller triangle is needed. Notation This leads to the simple notation n: a,b,c \text{ s.t. } a \ge b \ge c \ge 0 \And a+b+c \le n Where n is the size of the full triangle, and a,b,c are the sizes of the small triangles removed. They are in order for simplicity. They cannot add to more then n for two reasons, one, if a+b>n , they will overlap, which means n is not the minimum that it could be. And two, if a+b+c>n , then the other triangle is smaller. List of convex iamond blocks Size The number of base triangles in a triangle of length n is n^2 . The area is then simply \text{area} = n^2-a^2-b^2-c^2\, Enumeration Finding all blocks of a given size, N , is more difficult, as it is a difference of squares. The simplest method is to vary n between \sqrt{N} and N/2 , and find any a,b,c with squares that add to n^2 - N . The total number of blocks of size N is given by the sequence Parity The triangular grid can also be coloured alternating black and white, with each colour pointing in opposite directions( \blacktriangledown \vartriangle ). For a triangle, the colours match as diamonds, except for the triangles along the bottom of the large triangle, of which there are n . Removing the small triangles then reduce the parity by that much. So parity is simply \text{Parity} = n - a - b - c\, Polyhexes Polyhexes are based on hexagons. Because of their shape, hexagons cannot form true convex blocks, but they can form quasi-convex blocks that are based on the center of the hex. The basic structure is very similar to the truncated triangle model for polyiaminds, with just a few changes. Notation Similar to the polyiamonds n: a,b,c \text{ s.t. } a \ge b \ge c \ge 0 \And a+b+c < n Note the exception that a+b+c is strictly less then n . List of convex hex blocks Size The number of hexes in a triangle is n(n+1)/2 , so the formula for the area is similar but slightly more complex then the polyiamond version \text{area} = \frac{n(n+1)}{2} -\frac{a(a+1)}{2}-\frac{b(b+1)}{2}-\frac{c(c+1)}{2} Enumeration Finding all blocks of size N is not exceptionally hard, but is tedious and best left to a computer. Since it involves triangular numbers, exhaustive search is the simplest way to find them. The total number of blocks of size N is given by the sequence Parity The hex grid cannot be coloured in two colours in a regular manner, so parity is not a useful notion. Polytrihex Polytrihexes are based on the semiregular trihexagonal tiling. polytrihexes have a ration of 2:1 triangles to hexagons, so convex blocks need to have a similar ratio. Unfortunately, this limits the possible blocks to only parallelograms and trapezoids. Notation Since there are two different, distinct shapes that do not lend themselves to a single notation, such as with the triangles and hexagons, it is necessary to identify the shape, P for parallelogram, and T for trapezoid \text{P:}n \times m, 0 \text{T:}n \times m, 0 Note that n and m count the number of hexagons only. the triangles are required to maintain the correct ratio. Also, for the trapezoid, n=m forms an almost full triangle, except for the very top base triangle. Again, to maintain the correct ratio. Size The number of base trihex units in each block is equal to the number of hexagons, so is easy to calculate, with the trapezoid only slightly complex \text{P area} = nm\, \text{T area} = \frac{n(2m-n+1)}{2} Enumeration Finding all blocks of size N is relatively easy, as the parallelograms are the same as for the polyominoes blocks, and the trapezoids can be found from them. The procedure is # \forall x \text{ s.t. } x|N, x \le \sqrt{N} # \text{Let }y={N \over x} # \text{Then } n=x \text{ and } m=y \text{ gives P:}n \times m # \text{If } x \text{ is odd then } n=x \text{ and } m={2y+x-1 \over 2} \text{ gives T:}n \times m # \text{If } y \text{ is odd and } x \ne y \text{ then } n=\min (2x,y) \text{ and } m={y+2x-1 \over 2} \text{ gives T:}n \times m If x and y are both odd then it produces two different blocks unless they are equal. The case of x=1 produces the same n,m for both P and T. These shapes differ only in the position of the last \triangle on the end. For T, when n=m the shape is almost a triangle, except for the top \triangle . The total number of blocks of size N is given by the sequence (for the parallelograms) plus (for the trapezoids) Parity There is no parity colouring for the trihexagonal tiling Category:Block Fill